﻿// 力扣：62. 不同路径
// 链接：https://leetcode.cn/problems/unique-paths/description/

//方法：动态规划（虚拟行初始化）
//核心思路：通过虚拟行简化边界条件处理，两种初始化方式等价
class Solution
{
public:
    int uniquePaths(int m, int n)
    {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));   // 创建 (m+1)x(n+1) 的 DP 数组，多出的第0行和第0列作为虚拟边界

        //初始化选择（两种方式任选其一，逻辑等价）
        //方式1：虚拟右边界初始化（更符合直觉）
        //方式2：虚拟下边界初始化（代码对称性好）
        dp[0][1] = 1;                                           // 方式1：在起点的虚拟右侧放1个路径
        // dp[1][0] = 1;                                        // 方式2：在起点的虚拟下侧放1个路径

        // 状态转移：每个位置来自上方和左方的路径之和
        for (int i = 1; i <= m; ++i)                            // 从实际网格起点(1,1)开始计算
        {
            for (int j = 1; j <= n; ++j)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];         // 状态转移方程
            }
        }

        return dp[m][n];                                        // 返回右下角实际终点的路径数
    }
};
//关键点解释：
//1. 虚拟边界的作用：消除实际网格第一行和第一列的特殊判断
//    - 实际网格的(0,0)对应dp[1][1]
//    - 通过初始化虚拟相邻位置(dp[0][1]或dp[1][0])触发正确计算
// 
//2. 两种初始化方式的等价性证明：
//    - 初始化 dp[0][1]=1 时：
//    dp[1][1] = dp[0][1](1) + dp[1][0](0) = 1
//    - 初始化 dp[1][0]=1 时：
//    dp[1][1] = dp[0][1](0) + dp[1][0](1) = 1
//    - 两种方式都能正确初始化起点路径数
// 
//3. 空间优化提示：可压缩为一维数组，空间复杂度从 O(mn) 优化到 O(n)
//
//复杂度分析：
//时间复杂度：O(mn)  遍历整个二维网格
//空间复杂度：O(mn)  使用二维DP数组存储中间状态